package 队列宽搜;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

public class 二叉树的最大宽度 {
    public int widthOfBinaryTree(TreeNode root)
    {
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();// 用数组模拟队列
        q.add(new Pair<>(root,1));
        int  ret = 0 ;
        while(!q.isEmpty())
        {
            // 先更新这一层的宽度
            Pair<TreeNode,Integer> t1 = q.get(0);
            Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
            ret = Math.max(ret,t2.getValue()-t1.getValue()+1);
            // 让下一层进队
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> a : q)
            {
                TreeNode node = a.getKey();
                int index  = a.getValue();
                if(node.left!=null)
                {
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right !=null)
                {
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }

            }
            q = tmp;
        }
        return ret;
    }
}
